package arithmetic2.day07;

/*
    创建图的接口：将各种类型的图的表示方法转换为一种结构
 */
public class GeneratorGraph {
    /*
        将领接矩阵的表示方法转换为指定类型:
            二维数组的领接矩阵每一个数组的
                第一个元素代表出发点id
                第二个元素代表结束点id
                第三个元素代表权值
     */
    public static Graph matrixToGraph(int[][] matrix) {
        Graph graph = new Graph();
        //遍历matrix，每行代表一条边
        for (int i = 0; i < matrix.length; i++) {
            //获取出发点、结束点和权值
            int from = matrix[i][0];
            int to = matrix[i][1];
            int weight = matrix[i][2];
            //判断出发点和结束点是否已经存在
            if (!graph.nodes.containsKey(from)) {
                //不存在就创建这个节点，加入到nodes中
                Node node = new Node(from);
                graph.nodes.put(from, node);
            }
            if (!graph.nodes.containsKey(to)) {
                Node node = new Node(to);
                graph.nodes.put(to, node);
            }
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            //将from点的出度+1,to点添加到from点的直接子节点中
            fromNode.out++;
            fromNode.nexts.add(toNode);
            //将to点的入度+1
            toNode.in++;
            //创建边加入到from点的出发边中，加入到图中
            Edge edge = new Edge(weight, fromNode, toNode);
            fromNode.edges.add(edge);
            graph.edges.add(edge);
        }
        return graph;
    }

    public static void main(String[] args) {
//        bfs();
        dfs();
//        sortedTopology();
//        kruska();
    }

    //测试宽度优先遍历
    public static void bfs() {
        int[][] matrix = {
                {0, 1, 1},
                {1, 0, 1},
                {0, 2, 1},
                {2, 0, 1},
                {0, 4, 1},
                {4, 0, 1},
                {1, 2, 1},
                {2, 1, 1},
                {1, 4, 1},
                {4, 1, 1},
                {2, 3, 1},
                {3, 2, 1},
                {1, 3, 1},
                {3, 1, 1},
                {3, 4, 1},
                {4, 3, 1}
        };
        Graph graph = matrixToGraph(matrix);
        //从0开始宽度优先遍历
        graph.bfs(0);
    }

    //测试深度优先遍历
    public static void dfs() {
        int matrix[][] = {
                {0, 1, 1},
                {1, 0, 1},
                {0, 2, 1},
                {2, 0, 1},
                {0, 4, 1},
                {4, 0, 1},
                {1, 2, 1},
                {2, 1, 1},
                {2, 4, 1},
                {4, 2, 1},
                {2, 3, 1},
                {3, 2, 1},
                {3, 4, 1},
                {4, 3, 1}
        };
        Graph graph = matrixToGraph(matrix);
        //从0开始深度优先遍历
        graph.dfs(0);
    }

    //测试图的拓扑排序
    public static void sortedTopology(){
        int matrix[][] = {
                {0, 1, 1},
                {0, 2, 1},
                {1, 2, 1},
                {1, 3, 1},
                {2, 3, 1}
        };
        Graph graph = matrixToGraph(matrix);
        graph.sortedTopology();
    }

    //测试kruska算法将图转换为最小生成树
    public static void kruska(){
        int matrix[][] = {
                {0, 1, 7},
                {1, 0, 7},
                {0, 2, 2},
                {2, 0, 2},
                {0, 3, 100},
                {3, 0, 100},
                {2, 3, 4},
                {3, 2, 4},
                {1, 3, 1000},
                {3, 1, 1000},
                {1, 4, 100000},
                {4, 1, 100000}
        };
        Graph graph = matrixToGraph(matrix);
        Graph kruska = graph.kruska();
        System.out.println(kruska);
    }
}
